Corelab Seminar
2018-2019
Dimitris Myrisiotis
Circuits, Lower Bounds, and Circuit Analysis Algorithms
Abstract.
We survey the connections between circuit lower bounds and circuit analysis algorithms. Circuit analysis algorithms include, for example, satisfiability algorithms, compression algorithms, learning algorithms, or natural properties (which are algorithms that discriminate between functions computable in some specific circuit class and random functions). Recent work has indicated the importance of this direction by providing new intriguing ways of looking at old results as well as guidelines on acquiring new. In this talk, we pose some open problems that pertain to these connections between algorithms and lower bounds and discuss potential ways of approaching them.